<!DOCTYPE html>
<html>

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <title>标题</title>
</head>

<body>
    <script>
        /* 
            1.核心思路：
            将数组分成若干子序列，对每个子序列进行插入排序；比如，先对数组进行两两分组 长度 / 2，在进行直接插入排序 工作量非常小】；
            然后再 把跨度/2，设置为2，再两两分组，在排序
            2.时间复杂度平均情况小于O(n ^ 2)
            最差O(n ^ 2) [2,1,5,3,7,6,9,8] => 每次组内分组时，都无法进行深度的排序
            空间复杂度O(1) 每次let temp = nums[i] 每次又都会销毁
            3.不是原地排序 有用到临时变量 -> 有用到临时变量就不叫临时变量了？
            4.不是稳定排序 有可能影响相同元素前后的相对位置
              优化：分组每一轮的增量“互质”，而不是简单的1,2,4,
              HIbbard增量：1,3，7，15 => O(n ^ 3/2)
              Sedgewick增量：1,5,19 => O(n ^ 4/3) 
        */
        function shellSort(nums) {
            let gap = Math.floor(nums.length / 2); // 初始增量
            while (gap > 0) {
                // 对每个增量分组进行插入排序
                for (let i = gap; i < nums.length; i++) {
                    let temp = nums[i]; // 当前要插入的元素
                    let j = i; // 用于回溯的索引
                    // 在当前增量的分组中进行插入排序
                    while (j >= gap && nums[j - gap] > temp) {
                        nums[j] = nums[j - gap]; // 移动元素
                        j -= gap; // 回溯
                    }
                    nums[j] = temp; // 插入当前元素
                }
                gap = Math.floor(gap / 2); // 减小增量
            }
            return nums;
        }
        // console.log(shellSort([5, 3, 9, 12, 6, 1, 7, 2, 4, 11, 8, 10]));
        console.log(shellSort([5, 8, 6, 3, 9, 2, 1, 7]));
    </script>

</body>

</html>